package combination;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. 组合总和 III
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 *
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 * @author luolidong
 * @version 1.0
 * @create 2021-08-01 17:27
 */
public class L216 {
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k,n,new ArrayList<>(),1);
        return list;
    }
    public void dfs(int k, int n,List<Integer> clist,int start){
        if(clist.size()==k){
            int sum=0;
            for(int c:clist){
                sum+=c;
            }
            if(sum==n){
                list.add(new ArrayList<>(clist));
            }
            return;
        }
        for (int i = start; i <=9 ; i++) {
//            if(clist.contains(i)) continue;
            clist.add(i);
            dfs(k, n, clist, i+1);
            clist.remove(clist.size()-1);
        }
    }

    public static void main(String[] args) {
        L216 l216 = new L216();
        List<List<Integer>> list = l216.combinationSum3(4, 20);
        list.forEach(System.out::println);
    }
}
